package org.usmile.algorithms.leetcode.middle;

import org.usmile.algorithms.leetcode.ListNode;

/**
 * 92. 反转链表 II
 *
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 *
 * 示例 1：
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 *
 * 示例 2：
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 *
 * 提示：
 * 链表中节点数目为 n
 * 1 <= n <= 500
 * -500 <= Node.val <= 500
 * 1 <= left <= right <= n
 *
 * 进阶： 你可以使用一趟扫描完成反转吗？
 */
public class _0092 {
}

// 头插法
class _0092_Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;

        ListNode prev = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }

        ListNode curr = prev.next;
        for (int i = 0; i < right - left; i++) {
            ListNode next = curr.next;
            curr.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }

        return dummyNode.next;
    }
}

class _0092_Solution1 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) {
            return head;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode prevHead = dummy;
        ListNode reverseTail = head;
        int i = 1;
        for (; i < left; i++) {
            prevHead = prevHead.next;
            reverseTail = reverseTail.next;
        }

        ListNode reversePrev = null;
        ListNode reverseCurr = reverseTail;
        ListNode reverseNext = null;
        for (; i <= right; i++) {
            reverseNext = reverseCurr.next;
            reverseCurr.next = reversePrev;
            reversePrev = reverseCurr;
            reverseCurr = reverseNext;
        }
        prevHead.next = reversePrev;
        reverseTail.next = reverseNext;

        return dummy.next;
    }
}
